/**
 * Created by L.jp
 * Description:小东所在公司要发年终奖，而小东恰好获得了最高福利，他要在公司年会上参与一个抽奖游戏，游戏在一个6*6的棋盘上进行，
 * 上面放着36个价值不等的礼物，每个小的棋盘上面放置着一个礼物，他需要从左上角开始游戏，每次只能向下或者向右移动一步，到达右下角停止，一路上的格子里的礼物小东都能拿到，
 * 请设计一个算法使小东拿到价值最高的礼物。
 *
 * 给定一个6*6的矩阵board，其中每个元素为对应格子的礼物价值,左上角为[0,0],请返回能获得的最大价值，保证每个礼物价值大于100小于1000。
 * User: 86189
 * Date: 2022-03-20
 * Time: 13:57
 */
public class Bonus {
    //最大值问题，也是经典的动态规划问题，要求到达右下角的最大价值，那么子问题就是到达某个点的最大价值
    //由于只能往下或者往右走，所以到达每一个点的到达只有两种方式，要么是从他的上面，要么从他左边，所以只需取他们当中的一个最大值
    //状态初始化就是第一行只能由左边的点到达，第一列只能由上边的点到达
    public static  int getMost(int[][] board) {
        int row=board.length;
        int col = board[0].length;
        //初始化,列
        for(int i = 1; i <col ; i++){
            board[0][i]+=board[0][i-1];  //第一列的每个点都由他上面的点的最大价值累加而来
        }
        //初始化，行
        for(int j=1;j<row; j++){
            board[j][0] += board[j-1][0];
        }
        //构造剩余数组的位置
        for(int i = 1; i < row; i++){
            for(int j = 1; j < col; j++){
                board[i][j]+=Math.max(board[i-1][j],board[i][j-1]);
            }
        }
        return board[row-1][col-1];
    }

    public static void main(String[] args) {
        int[][]board={{200,300,400},{200,400,400},{300,400,500}};
        System.out.println(getMost(board));
    }
}
